"""
在给定的二维二进制数组A中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将0变为1，以使两座岛连接起来，变成一座岛。
返回必须翻转的0 的最小数目。（可以保证答案至少是 1 。）

示例 1：
输入：A = [[0,1],[1,0]]
输出：1
示例 2：
输入：A = [
        [0, 1, 0],
        [0, 0, 0],
        [0, 0, 1]
    ]
输出：2
示例 3：
输入：A = [
        [1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1]
    ]
输出：1

链接：https://leetcode-cn.com/problems/shortest-bridge
"""
import collections
from mode import List


class Solution:
    def shortestBridge(self, grid):
        m, n = len(grid), len(grid[0])
        steps = 0
        que = []

        def dfs(i, j):
            # 判断越界
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0 or grid[i][j] == 2:
                return
            grid[i][j] = 2
            que.append((i, j))
            # 四个方向遍历
            for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                newX, newY = x + i, y + j
                dfs(newX, newY)

        find = False
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not find:
                    dfs(i, j)
                    find = True
        # bfs
        while que:
            length = len(que)
            for _ in range(length):
                i, j = que.pop(0)
                for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                    newX, newY = x + i, y + j
                    if newX < 0 or newX >= len(grid) or newY < 0 or newY >= len(grid[0]) or grid[newX][newY] == 2:
                        continue
                    if grid[newX][newY] == 1:
                        return steps
                    grid[newX][newY] = 2
                    que.append((newX, newY))
            steps += 1
        return steps


if __name__ == "__main__":
    A = Solution()
    nums = [
        [0, 1, 0],
        [0, 0, 0],
        [0, 0, 1]
    ]
    nums2 = [
        [1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1],
        [1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1]
    ]
    print(A.shortestBridge(nums))

    # A = Solution1()
    # nums = [1, 2, 3]
    # print(A.permute(nums))
